蟻本2-5 Roadblocks

code: python

import heapq

MAX_N = 5000

MAX_R = 100000

INF = float('inf')

# 入力

N, R = map(int,input().split())

G = [[] for _ in range(MAX_N)] # グラフの隣接リスト表現

for i in range(R):

s, t, c = map(int,input().split())

Gs-1.append(t-1, c)

Gt-1.append(s-1, c)

# print(G)

# [1, 100, 0, 100], 2, 250, [3, 200, 1, 250], [3, 100, 1, 200], [2, 100, [], [], [],...]

que = []

dist = INF * MAX_N # 最短経路

dist2 = INF * MAX_N # 二番目の最短経路

dist0 = 0

heapq.heappush(que, 0, 0)

while len(que) != 0:

p = heapq.heappop(que)

# 最短距離

d = p0

# 位置

v = p1

if dist2v < d:

continue

# vからのルートを順番に検討

for i in range(len(Gv)):

e = Gvi

# vまでの最短　＋　次へのコスト

d2 = d + e1

# 現時点での次までの最短より、v経由でのコストが小さい場合（最短＞v経由でのコスト）

if dist[e0] > d2:

# 二つの値を入れ替え（最短と２番目の最短を更新）

dist[e0], d2 = d2, dist[e0]

# 次までの最短距離を優先度付きキューに格納

heapq.heappush(que, [dist[e0], e0])

# 現時点での２番目の最短より、v経由でのコストが小さいかつ、、

# 現時点での最短より、v経由でのコストが大きいとき（最短＜v経由のコスト＜２番目の最短）

if dist2[e0] > d2 and dist[e0] < d2:

# ２番目の最短を更新

dist2[e0] = d2

heapq.heappush(que, [dist2[e0], e0])

print(dist2N - 1)

# 4 4

# 1 2 100

# 2 3 250

# 2 4 200

# 3 4 100

テーマ

#dfs